/*
问题描述

　　中缀表达式就是我们通常所书写的数学表达式，后缀表达式也称为逆波兰表达式，在编译程序对我们书写的程序中的表达式进行语法检查时，往往就可以通过逆波兰表达式进行。我们所要设计并实现的程序就是将中缀表示的算术表达式转换成后缀表示，例如，将中缀表达式

(A 一 (B*C 十 D)*E) ／ (F 十 G )

转换为后缀表示为：ABC*D十E*--FG十／

注意：为了简化编程实现，假定变量名均为单个字母，运算符只有＋，－，＊，／ 和＾（指数运算，要注意运算符的结合性），可以处理圆括号 (），并假定输入的算术表达式正确。

要求：使用栈数据结构实现 ，输入的中缀表达式以＃号结束

输入
整数N。表示下面有N个中缀表达式
N个由单个字母和运算符构成的表达式

输出
N个后缀表达式。
*/

/*
测试用例1:
输入：
1
(A-(B*C+D)*E)/(F+G)#
输出：
ABC*D+E*-FG+/↵

测试用例2:
输入：
2
a+b*c-d#
a-b*(c+d)#
输出：
abc*+d-↵
abcd+*-↵
*/
#include <iostream>
#include <queue>
#include <map>
#include <stack>
#include <string>

using namespace std;

int main()
{
  // N个中缀表达式
  int N;
  cin >> N;
  
  // 存储N个中缀表达式
  string infix_expression;
  queue<string> infix_expressions;
  
  // 构建价值表
  map<char, int> value = {
    {'(', 0},
    {'+', 1},
    {'-', 1},
    {'*', 2},
    {'/', 2},
    {'^', 3},
  };
  
  // 读取用户输入
  for (int i=0; i<N; i++)
  {
    cin >> infix_expression;
    infix_expressions.push(infix_expression);
  }

  // 遍历N个中缀表达式
  while( !infix_expressions.empty() )
  {
    // 存储后缀表达式
    string postfix_expression;
    
    // 辅助栈
    stack<char> myStack;
    
    // 读取中缀表达式
    infix_expression = infix_expressions.front();
    
    // 出队
    infix_expressions.pop();
    
    for (char c : infix_expression)
    {
      // c是字母，直接加入后缀表达式
      if ((c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z'))
      {
        postfix_expression.push_back(c);
      }
      
      // c是左括号，直接入栈
      else if (c == '(')
      {
        myStack.push(c);
      }
      
      // c是右括号，栈内元素出栈，直到遇见左括号或者栈空
      else if (c == ')')
      {
        while(!myStack.empty())
        {
          // 读取栈顶元素
          char n = myStack.top();
          
          // 不为左括号，则添加进后缀表达式
          if (n != '(')
            postfix_expression.push_back(n);
          else
          {
            myStack.pop();
            break;
          }
          myStack.pop();
        }
      }
      
      // c是结束标志符，栈内元素全部添加进后缀表达式
      else if (c == '#')
      {
        while(!myStack.empty())
          {
            // 读取栈顶元素
            char n = myStack.top();
            
            // 添加进后缀表达式
            postfix_expression.push_back(n);
            
            myStack.pop();
          }
      }
      
      // c是运算符
      else 
      {
        while(!myStack.empty())
          {
            // 读取栈顶元素
            char n = myStack.top();
            
            // c运算优先级比n高 ，c入栈
            if (value[c] > value[n])
            {
              myStack.push(c);
              break;
            }
            // 添加进后缀表达式
            postfix_expression.push_back(n);
            
            myStack.pop();
          }
        
        // 栈为空，c入栈
        if (myStack.empty())
        {
          myStack.push(c);
        }
      }
    }
    
    cout << postfix_expression << endl;
  }
  
  return 0;
}